import java.util.ArrayList;

public class Board {

	public int[][] key;// ANSWER KEY(COMPLETED BOARD)
	public int[][] userBoard;// USERS BOARD
	public int[][] solver;

	private final int[] nums;// ARRAY CONTAINING 1-9

	// Constructs board, initally all set to zero.
	public Board() {
		key = new int[9][9];
		nums = new int[9];
		userBoard = new int[9][9];
		for (int i = 1; i <= 9; i++)
			nums[i - 1] = i;

	}

	// Returns array of remaining valid integers, where arr is numbers already
	// in a row/col/box
	private int[] getNums(int[] arr) {
		ArrayList<Integer> valid = new ArrayList<Integer>();
		for (int i = 0; i < nums.length; i++)
			valid.add(nums[i]);
		for (int i = 0; i < arr.length; i++) {
			valid.remove(new Integer(arr[i]));

		}
		int[] temp = new int[valid.size()];
		for (int i = 0; i < temp.length; i++)
			temp[i] = valid.get(i);

		return temp;

	}

	// Returns an array containing the values in Row row
	private int[] getRow(int row) {
		return key[row];

	}

	// Returns an array containing the values in Col col
	private int[] getCol(int col) {
		int[] temp = new int[key.length];
		for (int i = 0; i < key.length; i++)
			temp[i] = key[i][col];
		return temp;
	}

	// Returns an array containing the values in the Box that contains row, col
	private int[] getBox(int row, int col) {
		int i, j, t = 0;
		int[] temp = new int[key.length];

		i=(row/3)*3;
		j=(col/3)*3;

		for (int k = i; k < i + 3; k++) {
			for (int l = j; l < j + 3; l++) {

				temp[l % 3 + t] = key[k][l];

			}
			t += 3;
		}
		return temp;

	}

	// Returns true if num is in arr
	private boolean contains(int[] arr, int num) {

		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == num)
				return true;

		}
		return false;
	}

	// returns an array of the numbers contained in each, arr1, arr2, arr3
	private int[] crossCheck(int[] arr1, int[] arr2, int[] arr3) {
		ArrayList<Integer> arr = new ArrayList<Integer>();
		int[] temp;

		for (int i = 0; i < arr1.length; i++) {
			if (contains(arr2, arr1[i]) && contains(arr3, arr1[i]))
				arr.add(arr1[i]);
		}

		temp = new int[arr.size()];
		for (int i = 0; i < temp.length; i++)
			temp[i] = arr.get(i);

		return temp;

	}

	// Creates the board assignment
	public static Board creator() {
		Board b = new Board();
		while (b.assign() == -1) {
			b = new Board();
		}
		b.userBoard(30);
		return b;

	}

	// Attempts to assign the board, returning -1 if failure, 0 if successs
	private int assign() {

		int[] row, col, box, cross;
		int index;
		for (int i = 0; i < key.length; i++) {
			for (int j = 0; j < key.length; j++) {

				row = getNums(getRow(i));
				col = getNums(getCol(j));
				box = getNums(getBox(i, j));
				cross = crossCheck(row, col, box);

				if (cross.length == 0) {
					return -1;
				}
				index = (int) (Math.random() * cross.length);

				key[i][j] = cross[index];

			}

		}
		return 0;

	}

	// TEsts if it is ok to remove an element at i,j.
	private boolean testRemove(int i, int j) {
		int[][] temp = key;
		key = userBoard;
		int num = userBoard[i][j];
		userBoard[i][j] = 0;
		int[] row = getNums(getRow(i));
		int[] col = getNums(getCol(j));
		int[] box = getNums(getBox(i, j));
		int[] cross = crossCheck(row, col, box);
		key = temp;
		if (cross.length == 1) {
			userBoard[i][j] = num;
			return true;
		}
		userBoard[i][j] = num;
		return false;

	}

	// Reassigns userBoard to key, then attempts to remove elements based on
	// DIFFICULTY. 1<=Difficulty<=3
	public void userBoard(int dif) {
		int num, num2,DIFFICULTY;
		DIFFICULTY = dif;
		for (int i = 0; i < key.length; i++) {
			for (int j = 0; j < key.length; j++) {
				userBoard[i][j] = key[i][j];
			}
		}
		
		
		
		for(int i=0;i<20;i++)
		{
			num = (int) (Math.random() * 4)+1;
			num2 = (int) (Math.random() * 4)+1;
			userBoard[key.length/2+num2][key.length/2+num]=0;
			userBoard[key.length/2-num2][key.length/2-num]=0;
			userBoard[key.length/2+num2][key.length/2-num]=0;
			userBoard[key.length/2-num][key.length/2+num2]=0;
			int[][] temp=new int[9][9];
			for(int k=0;k<9;k++)
			{
				for(int j=0;j<9;j++)
				{
					temp[k][j]=userBoard[k][j];
				}
			}
			solve(temp);
			if(!win(temp))
			{
				userBoard[key.length/2+num][key.length/2+num]=key[key.length/2+num][key.length/2+num];
				userBoard[key.length/2-num][key.length/2-num]=key[key.length/2-num][key.length/2-num];
				userBoard[key.length/2+num][key.length/2-num]=key[key.length/2+num][key.length/2-num];
				userBoard[key.length/2-num][key.length/2+num]=key[key.length/2-num][key.length/2+num];
			}
			
			
			
			
			
		}
		


	}

	// Prints user board, where 0's represent blanks.
	public void printBoard(int[][] arr) {
		for (int i = 0; i < key.length; i++) {

			for (int j = 0; j < key.length; j++) {
				System.out.print(arr[i][j] + " ");
			}
			System.out.println();
		}

	}

	// Outputs board
	public String toString() {

		String temp = "";
		for (int i = 0; i < key.length; i++) {
			for (int j = 0; j < key.length; j++) {
				temp += key[i][j] + " ";
			}
			temp += "\n";
		}

		return temp;

	}

	// Attempts to assign the value num, to userBoard[row][col], provided
	// 1<=num<=9 and the space is empty
	public void Move(int num, int row, int col) {
		if (num > 0 && num < 10 && userBoard[row][col] == 0) {
			userBoard[row][col] = num;
		}

	}

	// Returns true if the user has won the game.
	public boolean win(int[][] user) {

		for (int i = 0; i < key.length; i++) {

			for (int j = 0; j < key.length; j++) {
				if (key[i][j] != user[i][j])
					return false;
			}
		}
		return true;
	}
	
	private int[][] copy(int[][] arr)
	{
		int[][] temp=new int[9][9];
		for (int i = 0; i < key.length; i++) {
			for (int j = 0; j < key.length; j++) {
				temp[i][j]=arr[i][j];
			}
		}
		return temp;
	}
//	//Returns true, if a solution is generated
//	private boolean guess(int[][] board, int[] cross, int row, int col){
//		
//		int[][] temp=copy(board);
//		
//		for(int i=0;i<cross.length;i++)
//		{
//			temp[row][col]=cross[i];
//			if(solver(temp))
//			{
//				board=temp;
//				return true;
//				
//			}
//				
//			temp[row][col]=0;
//			
//			
//			
//		}
//		return false;
//		
//		
//		
//	}
//	//Returns true if the puzzle can be solved in current configuration
//	private boolean solver(int[][] board)
//	{
//		int[][] temp = key;
//		key = board;
//		int[] cross=new int[1];
//		for(int k=0;k<key.length*key.length;k++) {
//
//			for (int i = 0; i < key.length; i++) {
//
//				for (int j = 0; j < key.length; j++) {
//					int[] row = getNums(getRow(i));
//					int[] col = getNums(getCol(j));
//					int[] box = getNums(getBox(i, j));
//					cross = crossCheck(row, col, box);
//					if (cross.length == 1 && board[i][j] == 0)
//						board[i][j] = cross[0];
//	
//				}
//			}
//
//		}
//		key = temp;
//		for(int i=0;i<key.length;i++)
//		{
//			
//			for(int j=0;j<key.length;j++)
//			{
//				if(board[i][j]==0)
//					return false;
//			}
//		}
//		
//		return true;
//		
//		
//		
//		
//		
//	}
//	
	private int[] add(int[] arr, int[] arr2)
	{
		
		int[] temp=new int[arr.length+arr2.length];
		int i=0;
		for(i=i;i<arr.length;i++)
		{
			temp[i]=arr[i];
		}
		i++;
		for(i=i;i<temp.length;i++)
		{
			temp[i]=arr2[i%(arr.length-1)];
		}
		return temp;
		
		
		
	}
	public void solve(int[][] board) {

		int[][] temp = key;
		key = board;
		int[] cross=new int[1];
		for(int k=0;k<key.length*key.length;k++) {

			for (int i = 0; i < key.length; i++) {

				for (int j = 0; j < key.length; j++) {
					int[] row = getNums(getRow(i));
					int[] col = getNums(getCol(j));
					int[] box = getNums(getBox(i, j));
					cross = crossCheck(row, col, box);
					if (cross.length == 1 && board[i][j] == 0)
						board[i][j] = cross[0];
					if(cross.length>1)
					{
						
						
						
						for(int l=(i/3)*3;l<(i/3)*3+3;l++)
						{
							for(int x=(j/3)*3;x<(j/3)*3+3;x++)
							{
								if(board[l][x]==0)
									cross=crossCheck(add(getRow(l),getCol(x)),cross,nums);
									
								
								
								
							}
							
							
							
						}
						if(cross.length==1&& board[i][j] == 0)
						{
							board[i][j]=cross[0];
						}
						
						
//						if(j%3==0)
//							{
//								
//								if(board[i][j+1]==0)
//									cross=crossCheck(cross,getCol(j+1),nums);
//								if(board[i][j+2]==0)
//									cross=crossCheck(cross,getCol(j+2),nums);
//
//							}
//							if(j%3==1)
//							{
//								if(board[i][j-1]==0)
//									cross=crossCheck(cross,getCol(j-1),nums);
//								if(board[i][j+1]==0)
//									cross=crossCheck(cross,getCol(j+1),nums);
//								
//								
//								
//							}
//							if(j%3==2)
//							{
//								if(board[i][j-1]==0)
//									cross=crossCheck(cross,getCol(j-1),nums);
//								if(board[i][j-2]==0)
//									cross=crossCheck(cross,getCol(j-2),nums);
//							}
//							if(i%3==0)
//							{
//								
//								if(board[i+1][j]==0)
//									cross=crossCheck(cross,getRow(i+1),nums);
//								if(board[i+2][j]==0)
//									cross=crossCheck(cross,getRow(i+2),nums);
//
//							}
//							if(i%3==1)
//							{
//								
//								if(board[i+1][j]==0)
//									cross=crossCheck(cross,getRow(i+1),nums);
//								if(board[i-1][j]==0)
//									cross=crossCheck(cross,getRow(i-1),nums);
//
//							}
//							if(i%3==2)
//							{
//								
//								if(board[i-1][j]==0)
//									cross=crossCheck(cross,getRow(i-1),nums);
//								if(board[i-2][j]==0)
//									cross=crossCheck(cross,getRow(i-2),nums);
//
//							}
//	
//						if(cross.length==1&&board[i][j]==0)
//						{
//							System.out.println(i+" "+j+" "+cross[0]);
//								board[i][j]=cross[0];
//						}
//			
					}
	
				}
			}

		}
		key = temp;
		
		


	}
}
	/*public int solve(int[][] board, int[] cros) {
		
								
	Solve
							
							
						

	}
}*/

/*
 * Remove one random element if testRemove works. If it does, remove another
 * element if testRemove works for that element, given the first element is in
 * place. Remove a third element if testRemove works provided the first two are
 * ok.
 */
